{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ec89c68b",
   "metadata": {},
   "source": [
    "## 3.2 何谓线性数据结构\n",
    "- 线性数据结构：一旦添加某个元素进来， 它与前后元素的相对位置将保持不变"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68408f23",
   "metadata": {},
   "source": [
    "## 3.3 栈\n",
    "### 3.3.1 何谓栈\n",
    "- 栈有时被称为“下推栈”，它是有序集合，添加操作和移除操作都在同一端，即：顶端，另一端则被称为底端\n",
    "- LIFO(last-in first-out):后进先出\n",
    "### 3.3.2 栈抽象数据类型\n",
    "- stack()：创建一个空栈\n",
    "- push(item):将一个元素添加到栈顶\n",
    "- pop()：将栈顶元素弹出\n",
    "- peek()：返回栈顶的元素\n",
    "- isEmpty()：检查栈是否为空\n",
    "- size()：返回栈中元素的数量\n",
    "### 3.3.3 用Python实践栈\n",
    "- 不推荐将列表的顶端作为栈的顶端，时间复杂度高"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a4030432",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "dog\n",
      "3\n",
      "False\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "#列表的底部作为栈的顶端\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "    \n",
    "    def pop(self):\n",
    "        return self.items.pop()\n",
    "    \n",
    "    def peek(self):\n",
    "        return self.items[len(self.items)-1]\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "s = Stack()\n",
    "print(s.isEmpty())\n",
    "s.push(4)\n",
    "s.push('dog')\n",
    "print(s.peek())\n",
    "s.push(True)\n",
    "print(s.size())\n",
    "print(s.isEmpty())\n",
    "s.push(8.4)\n",
    "s.pop()\n",
    "print(s.size())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a935044d",
   "metadata": {},
   "source": [
    "### 3.3.4 匹配括号\n",
    "- 括号匹配是指每一个左括号都有一个与之对应的右括号，并且有准确的嵌套关系"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "98d67732",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def parChecker(symbolString):\n",
    "    s = Stack()\n",
    "    balanced = True\n",
    "    index = 0\n",
    "    while index < len(symbolString) and balanced:\n",
    "        symbol = symbolString[index]\n",
    "        if symbol == \"(\":\n",
    "            s.push(symbol)\n",
    "        else:\n",
    "            if s.isEmpty():\n",
    "                balanced = False\n",
    "            else:\n",
    "                s.pop()\n",
    "        index+=1\n",
    "\n",
    "    if balanced and s.isEmpty():\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "print(parChecker(\"()())()\"))\n",
    "print(parChecker(\"(())()\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47acef58",
   "metadata": {},
   "source": [
    "### 3.3.5 普通情况：匹配符号 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "1ed9c0d0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def parChecker(sysmbolString):\n",
    "    s = Stack()\n",
    "\n",
    "    balanced = True\n",
    "    index= 0\n",
    "\n",
    "    while index < len(sysmbolString) and balanced:\n",
    "        symbol = sysmbolString[index]\n",
    "        if symbol in \"([{\":\n",
    "            s.push(symbol)\n",
    "        else:\n",
    "            if s.isEmpty():\n",
    "                balanced = False\n",
    "            else:\n",
    "                top = s.pop()\n",
    "                if not matches(top, symbol):\n",
    "                    balanced = False\n",
    "        index = index+1\n",
    "    if balanced and s.isEmpty():\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "def matches(open, close):\n",
    "    opens = \"([{\"\n",
    "    closes = \")]}\"\n",
    "\n",
    "    return opens.index(open) == closes.index(close)\n",
    "print(parChecker(\"()())()\"))\n",
    "print(parChecker(\"(())()\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28957b24",
   "metadata": {},
   "source": [
    "### 3.3.6 将十进制数转换成二进制数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "87d29e1c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10111\n",
      "55\n"
     ]
    }
   ],
   "source": [
    "def divideBy2(decNumber):\n",
    "    remstack = Stack()\n",
    "\n",
    "    while decNumber > 0:\n",
    "        rem = decNumber % 2\n",
    "        remstack.push(rem)\n",
    "        decNumber = decNumber // 2\n",
    "    binString = \"\"\n",
    "    while not remstack.isEmpty():\n",
    "        binString = binString + str(remstack.pop())\n",
    "    return binString\n",
    "print(divideBy2(23))\n",
    "#将十进制转换成任意进制\n",
    "def baseConverter(decNumber, base):\n",
    "    remstack1 = Stack()\n",
    "\n",
    "    while decNumber > 0:\n",
    "        rem = decNumber % base\n",
    "        remstack1.push(rem)\n",
    "        decNumber = decNumber // base\n",
    "    baseString = \"\"\n",
    "    while not remstack1.isEmpty():\n",
    "        baseString = baseString + str(remstack1.pop())\n",
    "    return baseString\n",
    "print(baseConverter(45, 8))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aeed8afa",
   "metadata": {},
   "source": [
    "### 3.3.7 前序、中序和后序表达式\n",
    "中序表达式  前序表达式  后续表达式\n",
    "A+B*C+D     ++A*BCD     ABC*+D+\n",
    "(A+B)*(C+D)  *+AB+CD    AB+CD+*\n",
    "A*B+C*D     +*AB*CD     AB*CD*+\n",
    "A+B+C+D     +++ABCD     AB+C+D+"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbbab8de",
   "metadata": {},
   "source": [
    "1. 从中序表达式向后序转换"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "251f513c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import string\n",
    "\n",
    "def infixToPostfix(infixexpr):\n",
    "    prec = {}\n",
    "    prec[\"*\"] = 3\n",
    "    prec[\"/\"] = 3\n",
    "    prec[\"+\"] = 2\n",
    "    prec[\"-\"] = 2\n",
    "    prec[\"(\"] = 1\n",
    "\n",
    "    opStack = Stack()\n",
    "    postfixList = []\n",
    "    tokenList = infixexpr.splite()\n",
    "\n",
    "    for token in tokenList:\n",
    "        if token in string.ascii_uppercase:\n",
    "            postfixList.append(token)\n",
    "        elif token == '(':\n",
    "            opStack.push(token)\n",
    "        elif token == ')':\n",
    "            topToken = opStack.pop()\n",
    "            while topToken != '(':\n",
    "                postfixList.append(topToken)\n",
    "                topToken = opStack.pop()\n",
    "        else:\n",
    "            while(not opStack.isEmpty()) and \\\n",
    "                (prec[opStack.peek()] >= prec[token]):\n",
    "                postfixList.append(opStack.pop())\n",
    "            opStack.push(token)\n",
    "    while not opStack.isEmpty():\n",
    "        postfixList.append(opStack.pop())\n",
    "\n",
    "    return \" \".join(postfixList)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8ee6ed4",
   "metadata": {},
   "source": [
    "2. 计算后序表达式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "fccf6c2a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['2', '7', '+', '9', '*']\n",
      "81\n"
     ]
    }
   ],
   "source": [
    "def postfixEval(postfixExpr):\n",
    "    openrandStack = Stack()\n",
    "\n",
    "    tokenList = postfixExpr.split()\n",
    "    print(tokenList)\n",
    "    for token in tokenList:\n",
    "        if token in \"0123456789\":\n",
    "            openrandStack.push(int(token))\n",
    "        else:\n",
    "            operand2 = openrandStack.pop()\n",
    "            operand1 = openrandStack.pop()\n",
    "            result = doMath(token, operand1, operand2)\n",
    "            openrandStack.push(result)\n",
    "    \n",
    "    return openrandStack.pop()\n",
    "def doMath(op, op1, op2):\n",
    "    if op == \"*\":\n",
    "        return op1*op2\n",
    "    elif op == \"/\":\n",
    "        return op1/op2\n",
    "    elif op == \"+\":\n",
    "        return op1+op2\n",
    "    else:\n",
    "        return op1-op2\n",
    "print(postfixEval(\"2 7 + 9 *\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63fcbe9c",
   "metadata": {},
   "source": [
    "## 3.4 队列\n",
    "### 3.4.1 何谓队列\n",
    "- FIFO(first-in first-out),先进先出\n",
    "### 3.4.2 队列抽象数据类型\n",
    "### 3.4.3 用Python实现队列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d5d48911",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queque:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def enqueue(self, item):\n",
    "        self.items.insert(0, item)\n",
    "    \n",
    "    def dequeue(self):\n",
    "        return self.items.pop()\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "282e56c5",
   "metadata": {},
   "source": [
    "### 3.4.4 模拟传土豆"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "55c6cc2f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Susan\n"
     ]
    }
   ],
   "source": [
    "def hotPotato(namelist, num):\n",
    "    simqueue = Queque()\n",
    "    for name in namelist:\n",
    "        simqueue.enqueue(name)\n",
    "    \n",
    "    while simqueue.size() > 1:\n",
    "        for i in range(num):\n",
    "            simqueue.enqueue(simqueue.dequeue())\n",
    "\n",
    "        simqueue.dequeue()\n",
    "\n",
    "    return simqueue.dequeue()\n",
    "print(hotPotato([\"Bill\", \"David\", \"Susan\", \"Jane\", \"Kent\", \"Brad\"], 7))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75a5e506",
   "metadata": {},
   "source": [
    "### 3.3.5 打印任务"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "73b93f4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Printer:\n",
    "    def __init__(self, ppm):\n",
    "        self.pagerate = ppm\n",
    "        self.currentTask = None\n",
    "        self.timeRemaining = 0\n",
    "    \n",
    "    def tick(self):\n",
    "        if self.currentTask != None:\n",
    "            self.timeRemaining = self.timeRemaining -1\n",
    "            if self.timeRemaining <= 0:\n",
    "                self.currentTask = None\n",
    "        \n",
    "    def busy(self):\n",
    "        if self.currentTask != None:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def startNext(self, newtask):\n",
    "        self.currentTask = newtask\n",
    "        self.timeRemaining = newtask.getPages() \\\n",
    "                            * 60/self.pagerate\n",
    "\n",
    "import random\n",
    "class Task:\n",
    "    def __init__(self, time):\n",
    "        self.timestamp = time\n",
    "        self.pages = random.randrange(1, 21)\n",
    "    \n",
    "    def getStamp(self):\n",
    "        "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
